.\" This file is dual-licensed.  Choose whichever you want.
.\"
.\" The first licence is a regular 2-clause BSD licence.  The second licence
.\" is the CC-0 from Creative Commons. It is intended to release Monocypher
.\" to the public domain.  The BSD licence serves as a fallback option.
.\"
.\" SPDX-License-Identifier: BSD-2-Clause OR CC0-1.0
.\"
.\" ----------------------------------------------------------------------------
.\"
.\" Copyright (c) 2017-2019, 2022-2023 Loup Vaillant
.\" Copyright (c) 2017-2018 Michael Savage
.\" Copyright (c) 2017, 2019-2023 Fabio Scotoni
.\" All rights reserved.
.\"
.\"
.\" Redistribution and use in source and binary forms, with or without
.\" modification, are permitted provided that the following conditions are
.\" met:
.\"
.\" 1. Redistributions of source code must retain the above copyright
.\"    notice, this list of conditions and the following disclaimer.
.\"
.\" 2. Redistributions in binary form must reproduce the above copyright
.\"    notice, this list of conditions and the following disclaimer in the
.\"    documentation and/or other materials provided with the
.\"    distribution.
.\"
.\" THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
.\" "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
.\" LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
.\" A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
.\" HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
.\" SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
.\" LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
.\" DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
.\" THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
.\" (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
.\" OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
.\"
.\" ----------------------------------------------------------------------------
.\"
.\" Written in 2017-2023 by Loup Vaillant, Michael Savage and Fabio Scotoni
.\"
.\" To the extent possible under law, the author(s) have dedicated all copyright
.\" and related neighboring rights to this software to the public domain
.\" worldwide.  This software is distributed without any warranty.
.\"
.\" You should have received a copy of the CC0 Public Domain Dedication along
.\" with this software.  If not, see
.\" <https://creativecommons.org/publicdomain/zero/1.0/>
.\"
.Dd February 25, 2023
.Dt CRYPTO_SIGN 3MONOCYPHER
.Os
.Sh NAME
.Nm crypto_eddsa_sign ,
.Nm crypto_eddsa_check ,
.Nm crypto_eddsa_key_pair ,
.Nm crypto_eddsa_to_x25519 ,
.Nm crypto_eddsa_trim_scalar ,
.Nm crypto_eddsa_reduce ,
.Nm crypto_eddsa_mul_add ,
.Nm crypto_eddsa_scalarbase ,
.Nm crypto_eddsa_check_equation
.Nd public key signatures
.Sh SYNOPSIS
.In monocypher.h
.Ft void
.Fo crypto_eddsa_sign
.Fa "uint8_t signature[64]"
.Fa "const uint8_t secret_key[64]"
.Fa "const uint8_t *message"
.Fa "size_t message_size"
.Fc
.Ft int
.Fo crypto_eddsa_check
.Fa "const uint8_t signature[64]"
.Fa "const uint8_t public_key[32]"
.Fa "const uint8_t *message"
.Fa "size_t message_size"
.Fc
.Ft void
.Fo crypto_eddsa_key_pair
.Fa "uint8_t secret_key[64]"
.Fa "uint8_t public_key[32]"
.Fa "uint8_t seed[32]"
.Fc
.Ft void
.Fo crypto_eddsa_to_x25519
.Fa "uint8_t x25519[32]"
.Fa "const uint8_t eddsa[32]"
.Fc
.Ft void
.Fo crypto_eddsa_trim_scalar
.Fa "uint8_t out[32]"
.Fa "const uint8_t in[32]"
.Fc
.Ft void
.Fo crypto_eddsa_reduce
.Fa "uint8_t reduced[32]"
.Fa "const uint8_t expanded[64]"
.Fc
.Ft void
.Fo crypto_eddsa_mul_add
.Fa "uint8_t r[32]"
.Fa "const uint8_t a[32]"
.Fa "const uint8_t b[32]"
.Fa "const uint8_t c[32]"
.Fc
.Ft void
.Fo crypto_eddsa_scalarbase
.Fa "uint8_t point[32]"
.Fa "const uint8_t scalar[32]"
.Fc
.Ft int
.Fo crypto_eddsa_check_equation
.Fa "const uint8_t Rs[64]"
.Fa "const uint8_t A[32]"
.Fa "const uint8_t h[32]"
.Fc
.Sh DESCRIPTION
.Ss High level API
.Fn crypto_eddsa_sign
and
.Fn crypto_eddsa_check
provide EdDSA public key signatures and verification.
.Fn crypto_eddsa_key_pair
computes the private and public keys from a random seed.
The arguments are:
.Bl -tag -width Ds
.It Fa seed
Random seed, freshly generated and used only once.
It is automatically wiped by
.Fn crypto_eddsa_key_pair .
See
.Xr intro 3monocypher
about random number generation (use your operating system's random
number generator).
.It Fa signature
The signature.
.It Fa secret_key
A secret key generated by
.Fn crypto_eddsa_key_pair ,
known only to you.
Internally the secret key is made up of the seed and the public key.
They are bundled together to avoid misuse,
and should be treated as a unit.
.It Fa public_key
The associated public key,
known to everyone.
.It Fa message
The message to sign.
.It Fa message_size
Length of
.Fa message ,
in bytes.
.El
.Pp
.Fa signature
and
.Fa message
may overlap.
.Pp
.Fn crypto_eddsa_sign
signs a message with
.Fa secret_key .
.Pp
.Fn crypto_eddsa_check
checks that a given signature is genuine.
Meaning, only someone who had the private key could have signed the
message.
.Sy \&It does not run in constant time .
It does not have to in most threat models because nothing is secret:
everyone knows the public key, and the signature and message are
rarely secret.
If the message needs to be secret, use
a key exchange protocol involving
.Xr crypto_x25519 3monocypher
and then
.Xr crypto_aead_lock 3monocypher
instead.
.Ss Conversion to X25519
.Fn crypto_eddsa_to_x25519
Converts and EdDSA public key to an X25519 public key.
Note that it ignores the sign of the
.Em x
coordinate of the EdDSA input.
The inverse operation is provided by
.Xr crypto_x25519_to_eddsa 3monocypher .
.Ss Low-level building blocks
.Fn crypto_eddsa_trim_scalar ,
.Fn crypto_eddsa_reduce ,
.Fn crypto_eddsa_mul_add ,
.Fn crypto_eddsa_scalarbase ,
and
.Fn crypto_eddsa_check_equation
provide low-level functionality to implement specialised APIs and
variants of EdDSA.
Monocypher uses them to implement all high-level EdDSA and Ed25519
functions.
.Pp
These functions are
.Sy dangerous ,
using them directly allows many kinds of catastrophic misuse.
The following descriptions are kept concise and technical on purpose.
If you do not understand them, do not not use those functions.
.Pp
.Fn crypto_eddsa_trim_scalar
reads a 256-bit number represented in little-endian,
and outputs the same number modified as follows:
the 3 least significant bits are cleared;
the most significant bit is cleared;
and the second most significant bit is set.
.Pp
.Fn crypto_eddsa_reduce
reads a 512-bit number represented in little-endian,
and outputs the same number reduced modulo the prime order of
Curve25519.
.Pp
.Fn crypto_eddsa_mul_add
reads three 256-bit numbers represented in little-endian,
and outputs
.Fa a
×
.Fa b
+
.Fa c ,
reduced modulo the prime order of Curve25519.
.Pp
.Fn crypto_eddsa_scalarbase
reads a 256-bit number represented in little-endian,
and outputs the result of the scalar multiplication between that number
and the twisted Edwards base point of Curve25519.
The output uses the same compressed representation as regular EdDSA
public keys:
the most significant bit represents the sign of the
.Em x
coordinate (1 if it is odd, 0 if it is even),
and the 255 other bits represent the
.Em y
coordinate in little-endian.
.Pp
.Fn crypto_eddsa_check_equation
reads a signature
.Fa \&Rs ,
a public_key
.Fa A ,
and hash
.Fa h ,
then checks the following:
.Bl -dash
.It
.Fa A
and
.Fa R
are both on the curve.
.It
.Fa s
is below the prime order of Curve25519.
.It
[8×s]B = [8]R + [8×h]A
.El
.Pp
It then returns 0 if all checks hold,
-1 otherwise.
Note that
.Fa A
and
.Fa R
are allowed to have low order,
and their encoding is allowed to be non-canonical.
.Sy This function does not run in constant time ,
do not use it with secret inputs.
.Sh RETURN VALUES
.Ss High level API
.Fn crypto_eddsa_key_pair
and
.Fn crypto_eddsa_sign
return nothing.
.Pp
.Fn crypto_eddsa_check
returns 0 for legitimate signatures and -1 for forgeries.
.Ss Conversion to X25519
.Fn crypto_eddsa_to_x25519
returns nothing.
.Ss Low-level building blocks
.Fn crypto_eddsa_trim_scalar ,
.Fn crypto_eddsa_reduce ,
.Fn crypto_eddsa_mul_add ,
and
.Fn crypto_eddsa_scalarbase
return nothing.
.Pp
.Fn crypto_eddsa_check_equation
returns 0 for legitimate signatures and -1 for forgeries.
.Sh EXAMPLES
The following examples assume the existence of
.Fn arc4random_buf ,
which fills the given buffer with cryptographically secure random bytes.
If
.Fn arc4random_buf
does not exist on your system, see
.Xr intro 3monocypher
for advice about how to generate cryptographically secure random bytes.
.Pp
Generate a key pair:
.Bd -literal -offset indent
uint8_t seed[32]; /* Random seed         */
uint8_t sk  [64]; /* secret key          */
uint8_t pk  [32]; /* Matching public key */
arc4random_buf(seed, 32);
crypto_eddsa_key_pair(sk, pk, seed);
/* Wipe the secret key if it is no longer needed */
/* The seed is wiped automatically               */
crypto_wipe(sk, 32);
.Ed
.Pp
Sign a message:
.Bd -literal -offset indent
uint8_t       sk       [64]; /* Secret key from above          */
const uint8_t message  [11] = "Lorem ipsu"; /* Message to sign */
uint8_t       signature[64];
crypto_eddsa_sign(signature, sk, message, 10);
/* Wipe the secret key if it is no longer needed */
crypto_wipe(sk, 32);
.Ed
.Pp
Check the above:
.Bd -literal -offset indent
const uint8_t pk       [32]; /* Their public key              */
const uint8_t message  [11] = "Lorem ipsu"; /* Signed message */
const uint8_t signature[64]; /* Signature to check            */
if (crypto_eddsa_check(signature, pk, message, 10)) {
	/* Message is corrupted, do not trust it */
} else {
	/* Message is genuine */
}
.Ed
.Pp
Implement XEdDSA
(signatures with X25519 keys normally used for key exchange)
with the low-level building blocks
.Bd -literal -offset indent
#include <monocypher.h>
#include <monocypher-ed25519.h>
#include <string.h>

void xed25519_sign(uint8_t signature[64],
                   const uint8_t secret_key[32],
                   const uint8_t random[64],
                   const uint8_t *message, size_t message_size)
{
	static const uint8_t zero   [32] = {0};
	static const uint8_t minus_1[32] = {
		0xec, 0xd3, 0xf5, 0x5c, 0x1a, 0x63, 0x12, 0x58,
		0xd6, 0x9c, 0xf7, 0xa2, 0xde, 0xf9, 0xde, 0x14,
		0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
		0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x10,
	};
	static const uint8_t prefix[32] = {
		0xfe, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
		0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
		0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
		0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
	};

	/* Key pair (a, A) */
	uint8_t A[32];  /* XEdDSA public key  */
	uint8_t a[32];  /* XEdDSA private key */
	crypto_eddsa_trim_scalar(a, secret_key);
	crypto_eddsa_scalarbase(A, a);
	int is_negative = A[31] & 0x80; /* Retrieve sign bit */
	A[31] &= 0x7f;                  /* Clear sign bit    */
	if (is_negative) {
		/* a = -a */
		crypto_eddsa_mul_add(a, a, minus_1, zero);
	}

	/* Secret nonce r */
	uint8_t r[64];
	crypto_sha512_ctx ctx;
	crypto_sha512_init  (&ctx);
	crypto_sha512_update(&ctx, prefix , 32);
	crypto_sha512_update(&ctx, a      , 32);
	crypto_sha512_update(&ctx, message, message_size);
	crypto_sha512_update(&ctx, random , 64);
	crypto_sha512_final (&ctx, r);
	crypto_eddsa_reduce(r, r);

	/* First half of the signature R */
	uint8_t R[32];
	crypto_eddsa_scalarbase(R, r);

	/* hash(R || A || M) */
	uint8_t H[64];
	crypto_sha512_init  (&ctx);
	crypto_sha512_update(&ctx, R      , 32);
	crypto_sha512_update(&ctx, A      , 32);
	crypto_sha512_update(&ctx, message, message_size);
	crypto_sha512_final (&ctx, H);
	crypto_eddsa_reduce(H, H);

	/* Signature */
	memcpy(signature, R, 32);
	crypto_eddsa_mul_add(signature + 32, a, H, r);

	/* Wipe secrets (A, R, and H are not secret) */
	crypto_wipe(a, 32);
	crypto_wipe(r, 32);
}

int xed25519_verify(const uint8_t signature[64],
                    const uint8_t public_key[32],
                    const uint8_t *message, size_t message_size)
{
	/* Convert X25519 key to EdDSA */
	uint8_t A[32];
	crypto_x25519_to_eddsa(A, public_key);

	/* hash(R || A || M) */
	uint8_t H[64];
	crypto_sha512_ctx ctx;
	crypto_sha512_init  (&ctx);
	crypto_sha512_update(&ctx, signature, 32);
	crypto_sha512_update(&ctx, A        , 32);
	crypto_sha512_update(&ctx, message  , message_size);
	crypto_sha512_final (&ctx, H);
	crypto_eddsa_reduce(H, H);

	/* Check signature */
	return crypto_eddsa_check_equation(signature, A, H);
}
.Ed
.Sh SEE ALSO
.Xr crypto_blake2b 3monocypher ,
.Xr crypto_x25519 3monocypher ,
.Xr crypto_aead_lock 3monocypher ,
.Xr intro 3monocypher
.Sh STANDARDS
.Fn crypto_eddsa_sign ,
.Fn crypto_eddsa_check ,
and
.Fn crypto_eddsa_key_pair
implement PureEdDSA with Curve25519 and BLAKE2b,
as described in RFC 8032.
This is the same as Ed25519, with BLAKE2b instead of SHA-512.
.Pp
.Fn crypto_eddsa_trim_scalar ,
.Fn crypto_eddsa_reduce ,
.Fn crypto_eddsa_mul_add ,
.Fn crypto_eddsa_scalarbase ,
and
.Fn crypto_eddsa_check_equation
can be used to implement any Curve25519 based EdDSA variant,
including Ed25519 and Ed25519ph.
.Sh HISTORY
The
.Fn crypto_sign ,
.Fn crypto_check ,
and
.Fn crypto_sign_public_key
functions appeared in Monocypher 0.2.
.Pp
Starting with Monocypher 2.0.5, modified signatures abusing the inherent
signature malleability property of EdDSA now cause a non-zero return
value of
.Fn crypto_check ;
in prior versions, such signatures would be accepted.
.Pp
.Sy A critical security vulnerability
that caused all-zero signatures to be accepted was introduced in
Monocypher 0.3;
it was fixed in Monocypher 1.1.1 and 2.0.4.
.Pp
In Monocypher 4.0.0
.Fn crypto_eddsa_trim_scalar ,
.Fn crypto_eddsa_reduce ,
.Fn crypto_eddsa_mul_add ,
.Fn crypto_eddsa_scalarbase ,
and
.Fn crypto_eddsa_check_equation
were added,
and the incremental and custom hash API removed.
The main interface was also reworked to avoid misuse,
and
.Fn crypto_eddsa_key_pair
replaced
.Fn crypto_sign_public_key .
.Sh CAVEATS
Monocypher does not perform any input validation.
Any deviation from the specified input and output length ranges results
in
.Sy undefined behaviour .
Make sure your inputs are correct.
.Sh SECURITY CONSIDERATIONS
.Ss Signature malleability
Signature malleability is the ability of an attacker to produce a valid
signature with knowledge of only an existing signature and the public
key.
Monocypher prevents that by checking the encoding of the signature,
and guarantees that generating new signatures requires the private key.
.Pp
On the other hand, EdDSA signatures are not unique like cryptographic
hashes.
The signing procedure is deterministic by specification and
.Fn crypto_eddsa_sign
follows this specification.
However, someone with the private key can generate arbitrarily many
valid, canonical, and different signatures of the same message.
Because of this, never assume that signatures are unique.
.Ss Fault injection and power analysis
Fault injection (also known as glitching) and power analysis may be used
to manipulate the resulting signature and recover the secret key in
some cases.
This requires hardware access.
We can try to mitigate this attack by prefixing all hashes a random data
block,
in a construction similar to Ed25519ctx.
Note that there may still be other power-related side channels (such as
if the CPU leaks information when an operation overflows a register)
that must be considered.
